package offer;

import baodian.Sort;
import common.ListNode;
import common.TreeNode;
import org.junit.Test;

import java.util.*;

import static common.Util.swap;

/**
 * @author fance
 * @date 18-4-19 下午1:05
 */
public class Solution {
    // dfs时使用
    private int[][] next = {{0,-1},{0,1},{-1,0},{1,0}};

    // 单例: 同目录下所有解决方案

    /**
     * 0~n - 1 数组中是否存在重复的数字
     * @param nums
     * @param len
     * @return
     */
    public boolean duplicate(int[] nums, int len, int[] dup) {
        for (int i = 0; i < len; i++) {
            while (nums[i] != i && nums[i] != nums[nums[i]]) {
                swap(nums, i, nums[i]);
            }
            if (nums[i] != i && nums[i] == nums[nums[i]]) {
                dup[0] = nums[i];
                return true;
            }
        }
        return false;
    }

    // 从尾到头打印链表 1.用集合保存 2. 递归 3.头插法
    public ArrayList<Integer> printListReverseI(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        while (listNode != null) {
            res.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(res);
        return res;
    }
    public ArrayList<Integer> printListReverseII(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode != null) {
            res.addAll(printListReverseII(listNode.next));
            res.add(listNode.val);
        }
        return res;
    }
    public ArrayList<Integer> printListReverseIII(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }
        ListNode head = null;
        ListNode cur = listNode;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head;
            head = cur;
            cur = next;
        }
        while (head != null) {
            res.add(head.val);
            head = head.next;
        }
        return res;
    }

    /**
     * 前序中序 重建二叉树
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reBuildBinaryTree(int[] pre, int[] in) {
       return reBuildBinaryTree(pre,0,pre.length - 1, in, 0, in.length - 1);
    }
    private TreeNode reBuildBinaryTree(int[] pre, int preL, int preR,int[] in, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preL]);
        if (preL != preR) {
            int index = inL;
            while (index <= inR && in[index] != root.val) {
                index++;
            }
            int leftTreeLen = index - inL;
            root.left = reBuildBinaryTree(pre, preL + 1, preL + leftTreeLen, in, inL, inL + leftTreeLen - 1);
            root.right = reBuildBinaryTree(pre, preL + leftTreeLen + 1, preR, in, inL + leftTreeLen + 1, inR);
        }
        return root;
    }

    // 中序遍历二叉树的下一个节点: 若有右子树 返回右子树根节点; 否则 向上找  parent.left = curNode ret parent

    // 两栈实现队列: stack1 进 stack2出   当stack2为空时,将stack1所有元素压入stack2 完成逆序.

    // 斐波那契数列: f(n - 1) + f(n - 2) ; 记忆化搜索 int[] fib; 动态规划 用两个变量

    // 跳台阶|| 矩形覆盖 同斐波那契数列; 变态跳台阶: 2 * f(n - 1)

    // 旋转数组中最小的数字: 1. 暴力搜索 2. 用旋转的特性,二分
    // I 适用与数字不重复  若存在重复 直接暴力搜索吧.
    public int minNumInRotateSortedArrayI(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        int lo = 0;
        int hi = nums.length - 1;
        int mid = lo;
        while (nums[lo] >= nums[hi]) {
            if ((hi - lo) == 1) {
                mid = hi;
                break;
            }

            mid = lo + (hi - lo) / 2;
            if (nums[mid] >= nums[lo]) {
                lo = mid;
            } else if (nums[mid] <= nums[hi]) {
                hi = mid;
            }
        }
        return nums[mid];
    }

    /**
     * 矩阵中的路径
     * @param maxtrix
     * @param rows
     * @param cols
     * @param str
     * @return
     */
    public boolean hasPath(char[][] maxtrix, int rows, int cols, char[] str) {
        if (rows == 0 || cols == 0) {
            return false;
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (backtrack(maxtrix, rows, cols, str,new boolean[rows][cols], 0 ,i,j)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean backtrack(char[][] maxtrix, int rows, int cols, char[] str, boolean[][] used,int path, int r, int c) {
        if (path == str.length) {
            return true;
        }
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }
        if (maxtrix[r][c] != str[path]) {
            return false;
        }
        if (used[r][c]) {
            return false;
        }
        used[r][c] = true;
        for (int i = 0; i < next.length; i++) {
            if (backtrack(maxtrix, rows, cols, str,used,path + 1,r + next[i][0], c + next[i][1])) {
                return true;
            }
        }
        used[r][c] = false;
        return false;
    }


    /**
     * 机器人的运动
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public int moveCnt(int threshold, int rows, int cols) {
        boolean[][] visited = new boolean[rows][cols];
        return moveCntCore(threshold, rows, cols, 0, 0, visited);
    }
    private int moveCntCore(int threshold, int rows, int cols, int row, int col, boolean[][] visited) {
         if (col < 0 || col > cols || row < 0 || row > rows) {
             return 0;
         }
         if (visited[row][col] || !checkSum(threshold, row, col)) {
             return 0;
         }
         visited[row][col] = true;
         int res = 1;
        for (int i = 0; i < next.length; i++) {
            res += moveCntCore(threshold, rows, cols, row + next[i][0], col + next[i][1],visited);
        }
        return res;
    }
    private boolean checkSum(int threshold, int row, int col) {
        int sum = 0;
        while (row != 0) {
            sum += row % 10;
            row /= 10;
        }
        while (col != 0) {
            sum += col % 10;
            col /= 10;
        }
        return sum < threshold;
    }

    /**
     * 剪绳子 1.dp  2.贪心
     * @param len
     * @return
     */
    public int cutRopeI(int len) {
        if (len < 2) {
            return 0;
        }
        if (len <= 3) {
            return len - 1;
        }
        int[] res = new int[len + 1];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        res[3] = 3;
        int max;
        for (int i = 4; i <= len; i++) {
            max = 0;
            for (int j = 1; j <= i / 2; j++) {
                int cur = res[j] * res[i - j];
                if (max < cur) {
                    max = cur;
                }

                res[i] = max;
            }
        }

        max = res[len];
        return max;
    }
    public int cutRopeII(int len) {
        if (len < 2) {
            return 0;
        }
        if (len <= 3) {
            return len - 1;
        }
        int timesOf3 = len / 3;
        if ((len - timesOf3 * 3) == 1) {
            timesOf3 -= 1;
        }
        int timesOf2 = (len - timesOf3 * 3) / 2;
        return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timesOf2);
    }

    /**
     * 打印1 到 n 的最大n 位数  1. 暴力 2. 转化 为全排列 (不太懂)
     * @param n
     */
    public void printToMaxOfNDigitsI(int n) {
        int num = 1;
        int i= 0;
        while (i++ < n) {
            num *= 10;
        }
        for (int j = 1; j < num; j++) {
            System.out.print(j + " ");
        }
    }
    public void printToMaxOfNDigitsII(int n) {
        if (n <= 0) {
            return;
        }
        int[] num = new int[n];
        backtrackForprintToMaxOfNDigitsII(num, 0);
    }
    private void backtrackForprintToMaxOfNDigitsII(int[] num,int index) {
        if (index != num.length) {
            for (int i = 0; i < 10; i++) {
                num[index] = i;
                backtrackForprintToMaxOfNDigitsII(num, index + 1);
            }
        } else {
            boolean flag = false;
            for (int i = 0; i < num.length; i++) {
                if (num[i] != 0) {
                    flag = true;
                }
                if (flag) {
                    System.out.print(num[i] + " ");
                }
            }
            if (flag) {
                System.out.println();
            }
        }
    }

    // o(1) 删除 链表节点: 复制后一个节点值,指向后后节点.若为尾节点没办法,只能o(n).
    public void delListNode(ListNode head, ListNode node) {
        if (head == null || node == null) {
            return;
        }
        if (node.next != null) {
            node.val = node.next.val;
            node.next = node.next.next;
        } else if (head == node) {
            head = null;
        } else { // 尾节点
            ListNode tmp = head;
            while (tmp.next != node) {
                tmp = tmp.next;
            }
            tmp.next = null;
            node = null; // let gc
        }
    }

    /**
     * 正则表达式匹配
     * @param str
     * @param pattern
     * @return
     */
    public boolean match(String str, String pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        return matchCore(str.toCharArray(), pattern.toCharArray());
    }
    private boolean matchCore(char[] str, char[] pattern) {
        int m = str.length;
        int n = pattern.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (pattern[i - 1] == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern[j - 1] == '*') {
                    if (pattern[j - 2] != str[i - 1] && pattern[j - 2] != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 判断是否为数值字符串
     * @param s
     * @return
     */
    public boolean isNum(String s) {
        if (s == null || s.length() < 1) {
            return false;
        }
        return s.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
    }

    /**
     * 调整奇数在偶数前面
     * @param arr
     */
    public void reOrderArray(int[] arr) {
        int oddCnt = 0;
        for (int num: arr
             ) {
            if (num % 2 != 0) {
                oddCnt++;
            }
        }
        int[] copy = arr.clone();
        int i = 0;
        int j = oddCnt;
        for (int num: copy
             ) {
            if (num % 2 != 0) {
                arr[i++] = num;
            } else {
                arr[j++] = num;
            }
        }
    }

    /**
     * 合并排序链表
     * @param listNode1
     * @param listNode2
     * @return
     */
     public ListNode MergeSortedList(ListNode listNode1, ListNode listNode2) {
        if (listNode1 == null) {
            return listNode2;
        }
        if (listNode2 == null) {
            return listNode1;
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val < listNode2.val) {
                cur.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                cur.next = listNode2;
                listNode2 = listNode2.next;
            }
            cur = cur.next;
        }
        if (listNode1 != null) {
            cur.next = listNode1;
        }
        if (listNode2 != null) {
            cur.next = listNode2;
        }
        return head.next;
     }

    /**
     * 树的子结构
     * @param root1
     * @param root2
     * @return
     */
     public boolean hasSubTree(TreeNode root1, TreeNode root2) {
        boolean res = false;
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                res = hasSubTreeCore(root1, root2);
            }
            if (!res) {
                res = hasSubTree(root1.left, root2);
            }
            if (!res) {
                res = hasSubTree(root1.right, root2);
            }
        }
        return res;
     }
     private boolean hasSubTreeCore(TreeNode root1, TreeNode root2) {
         if (root2 == null) {
             return true;
         }
         if (root1 == null) {
             return false;
         }
         if (root1.val != root2.val) {
             return false;
         }
         return hasSubTreeCore(root1.left , root2.left) && hasSubTreeCore(root1.right , root2.right);
     }


     public boolean isBalancedTree(TreeNode root) {
        return checkHeight(root) != -1;
     }
     private int checkHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = checkHeight(root.left);
        if (left == -1) {
            return -1;
        }
        int right = checkHeight(root.right);
        if (right == -1) {
            return -1;
        }

        int heightDiff = left - right;
        if (Math.abs(heightDiff) > 1){
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }
     }

     public boolean isPopOrder(int[] pushA, int[] popA) {
        int n = pushA.length;
         LinkedList<Integer> stack = new LinkedList<>();
         int j = 0;
         for (int i = 0; i < n; i++) {
             stack.push(pushA[i]);
             while (j < n && stack.peek() == popA[j]) {
                 stack.pop();
                 j++;
             }
         }
         return stack.isEmpty();
     }

     // 全排列  1.回溯 2. 交换
    public ArrayList<String> Permutation(String s) {
        ArrayList<String> res = new ArrayList<>();
        if (s.length() < 1) {
            return res;
        }
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        backtrack(chars,new boolean[chars.length], "", res);
        return res;
    }
    private void backtrack(char[] chars, boolean[] used, String s, ArrayList<String> res) {
        if (s.length() == chars.length) {
            res.add(s);
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i != 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            backtrack(chars, used, s + chars[i], res);
            used[i] = false;
        }
    }

    public void printStrPermutation(String s) {
        if (s == null) {
            return;
        }
        printStrPermutationCore(s.toCharArray(),0);
    }
    private void printStrPermutationCore(char[] s, int index) {
        if (index >= s.length) {
            return;
        }
         if (index == s.length - 1) {
            System.out.println(String.valueOf(s));
        } else {
            for (int i = index; i < s.length; i++) {
                swapForPermutation(s,i, index);
                printStrPermutationCore(s, index + 1);
                swapForPermutation(s,i, index);
            }

        }
    }
    private void swapForPermutation(char[] a, int i, int j) {
         char tmp = a[i];
         a[i] = a[j];
         a[j] = tmp;
    }

    // topK 1.sort 2. heap 3.quickSelect
    public ArrayList<Integer> minK(int[] arr, int k) {
        if (arr == null || k > arr.length) {
            return null;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((o1, o2) -> o2 - o1);
        for (int num: arr
                ) {
            maxHeap.offer(num);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }
    public ArrayList<Integer> minKII(int[] arr, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (arr == null || k > arr.length) {
            return res;
        }
        int st = 0;
        int end = arr.length - 1;
        int index = Sort.partition(arr, st, end);
        while (index != k - 1) {
            if (index > k - 1) {
                end = index - 1;
                index = Sort.partition(arr, st, end);
            } else {
                st = index + 1;
                index = Sort.partition(arr, st, end);
            }
        }
        for (int i = 0; i < k; i++) {
            res.add(arr[i]);
        }
        return res;
    }

    /**
     *  在排序数组中统计数字出现的次数  1.bf 2.二分
     * @param data
     * @param len
     * @param st
     * @param end
     * @return
     */
    public int getNumInSortedArrayFirst(int[] data,int len, int k,int st, int end) {
        if (st > end) {
            return -1;
        }
        int mid = st + (end - st) / 2;
        if (data[mid] == k) {
            if ((mid > 0 && data[mid - 1] != k) || mid == 0) {
                return mid;
            } else {
                end = mid - 1;
            }
        } else if (data[mid] > k) {
            end = mid - 1;
        } else {
            st = mid + 1;
        }

        return getNumInSortedArrayFirst(data, len, k, st, end);
    }
    public int getNumInSortedArrayLast(int[] data,int len, int k,int st, int end) {
        if (st > end) {
            return -1;
        }
        int mid = st + (end - st) / 2;
        if (data[mid] == k) {
            if ((mid < len - 1 && data[mid + 1] != k) || mid == len - 1) {
                return mid;
            } else {
                st = mid + 1;
            }
        } else if (data[mid] > k) {
            end = mid - 1;
        } else {
            st = mid + 1;
        }

        return getNumInSortedArrayLast(data, len, k, st, end);
    }
    public int getNumTimes(int[] data,int len, int k) {
        int times = 0;
        if (data != null && len > 0) {
            int first = getNumInSortedArrayFirst(data,len,k,0,len - 1);
            int last = getNumInSortedArrayLast(data,len,k,0,len - 1);
            if (first > -1 && last > -1) {
                times = last - first + 1;
            }
        }
        return times;
    }

    /**
     * 0-n-1  中缺失的数字 1.求和 2.二分
     * @param numbers
     * @return
     */
    public int getMissingNumI(int[] numbers) {
        if (numbers == null || numbers.length < 1) {
            return -1;
        }
        int n = numbers.length + 1;
        int expectSum = (0 + numbers.length) * n / 2; //因为n 为 n - 1; 有点绕,
        int realSum = 0;
        for (int i = 0; i < numbers.length; i++) {
            realSum += numbers[i];
        }
        return expectSum - realSum;
    }
    public int getMissingNumII(int[] numbers) {
        if (numbers == null || numbers.length < 1) {
            return -1;
        }
        int n = numbers.length;

        int lo = 0;
        int hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (numbers[mid] != mid) {
                if (mid == 0 || numbers[mid - 1] == mid - 1) {
                    return mid;
                }
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        if (lo == n) {
            return n;
        }
        return -1;
    }

    // 1.bf 2.二分  求魔术索引
    public int getNumSameAsIndex(int[] numbers) {
        if (numbers == null || numbers.length < 1) {
            return -1;
        }
        int lo = 0;
        int hi = numbers.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (numbers[mid] == mid) {
                return mid;
            }
            if (numbers[mid] > mid) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }

     // 二叉搜索树的第K个节点
     TreeNode ret;
     int cnt = 0;
     TreeNode kThNode(TreeNode root, int k) {
        inorder(root, k);
        return ret;
     }
     private void inorder(TreeNode root, int k) {
         if (root == null) {
             return;
         }
         if (cnt > k) {
             return;
         }
         inorder(root.left, k);
         cnt++;
         if (cnt == k) {
             ret = root;
         }
         inorder(root.right, k);
     }

     public int treeDepth(TreeNode root) {
         if (root == null) {
             return 0;
         }
         return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
     }

     // 数组中只出现一次的数: 1.一个数字: 异或 2.两个数字: diff &= -diff; 得到diff最右侧不为0 的位;
    public int[] findNumsAppearOnce(int[] a) {
         int e1 = 0;
        for (int num: a
             ) {
            e1 ^= num;
        }
        int eRightOne = e1 & (~e1 + 1);
        int e2 = 0;
        for (int num: a
             ) {
            if ((num & eRightOne) != 0) {
                e2 ^= num;
            }
        }
        int[] res = new int[2];
        res[0] = e2;
        res[1] = e1 ^ e2;

        return res;
     }

    /**
     * 连续子数组的最大和 1.暴力 2.贪心 3. 动态规划
     * @param a
     * @return
     */
     public int findGreatestSumOfSubArrayI(int[] a) {
         if (a == null || a.length < 1) {
             return 0;
         }
         int maxSum = a[0];
         for (int i = 0; i < a.length - 1; i++) {
             for (int j = i + 1; j < a.length; j++) {
                int curSum = calSum(a, i, j);
                if (curSum > maxSum) {
                    maxSum = curSum;
                }
             }
         }
         return maxSum;
     }
     private int calSum(int[] a, int st, int end) {
         int sum = 0;
         for (int i = st; i <= end; i++) {
             sum += a[i];
         }
         return sum;
     }

     public int findGreatestSumOfSubArrayII(int[] a) {
        if (a == null || a.length < 1) {
            return 0;
        }
        int maxSum = a[0];
        int curSum = 0;
        for (int i = 0; i < a.length; i++) {
            if (curSum <= 0) {
                curSum = a[i];
            } else {
                curSum += a[i];
            }
            if (curSum > maxSum) {
                maxSum = curSum;
            }
        }
        return maxSum;
    }

     public int findGreatestSumOfSubArrayIII(int[] a) {
         if (a == null || a.length < 1) {
             return 0;
         }
         int[] dp = new int[a.length];
         for (int i = 0; i < a.length; i++) {
             if (i == 0 || dp[i - 1] <= 0) {
                 dp[i] = a[i];
             }
             if (i != 0 && dp[i - 1] > 0) {
                 dp[i] = a[i] + dp[i - 1];
             }
         }
         int max = Integer.MIN_VALUE;
         for (int i = 0; i < dp.length; i++) {
             max = Math.max(dp[i], max);
         }
         return max;
     }

    /**
     * 1-n 整数中1 出现的次数
     * @param n
     * @return
     */
     public int numberOf1AppearTimes(int n) {
        int times = 0;
         for (int i = 1; i <= n; i++) {
             times += numberOf1(i);
         }
         return times;
     }
     private int numberOf1(int n) {
         int times = 0;
         while (n > 0) {
             if (n % 10 == 1) {
                 times++;
             }
             n /= 10;
         }
         return times;
     }


    /**
     * 把数组排列成最小的数 1. 全排列 求最小 2.排序
     */
    public void arrangeMinArray(Integer[] a) {
        Arrays.sort(a, (o1,o2) -> (o1 + "" + o2).compareTo(o2 + "" + o1));
    }

    /**
     * 最长不含重复字符的子字符串长度
     * @param s
     * @return
     */
    public int longestSubstringWithoutDup(String s) {
        int curLen = 0;
        int maxLen = 0;
        int[] position = new int[26];
        for (int i = 0; i < 26; i++) {
            position[i] = -1;
        }
        for (int i = 0; i < s.length(); i++) {
            int prevIndex = position[s.charAt(i) - 'a'];

            if (prevIndex < 0 || i - prevIndex > curLen) {
                curLen++;
            } else {
                if (curLen > maxLen) {
                    maxLen = curLen;
                }
                curLen = i - prevIndex;
            }

            position[s.charAt(i) - 'a'] = i;
        }

        if (curLen > maxLen) {
            maxLen = curLen;
        }
        return maxLen;
    }

    /**
     * 把数字翻译成字符串
     * @param number
     * @return
     */
    public int GetTranslationCount(int number) {
        if (number < 0) {
            return 0;
        }
        return GetTranslationCountCore(String.valueOf(number));
    }
    private int GetTranslationCountCore(String numberStr) {
        int len = numberStr.length();
        int[] counts = new int[len];
        int cnt;
        for (int i = len - 1; i >= 0; i--) {
            cnt = 0;
            if (i < len - 1) {
                cnt = counts[i + 1];
            } else {
                cnt = 1;
            }
            if (i < len - 1) {
                int digit1 = numberStr.charAt(i) - '0';
                int digit2 = numberStr.charAt(i + 1) - '0';
                int converted = digit1 * 10 + digit2;
                if (converted >= 10 && converted <= 25) {
                    if (i < len - 2) {
                        cnt += counts[i + 2];
                    } else {
                        cnt += 1;
                    }
                }
            }
            counts[i] = cnt;
        }
        return counts[0];
    }

    /**
     * 礼物的最大价值
     * @param values
     * @param rows
     * @param cols
     * @return
     */
    public int getMaxVal(int[][] values,int rows,int cols) {
        if (values == null || rows < 1 || cols < 1) {
            return 0;
        }
        int[][] dp = new int[rows][cols];
        dp[0][0] = values[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + values[i][0];
        }
        for (int i = 1; i < cols; i++) {
            dp[0][i] = dp[0][i - 1] + values[0][i];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + values[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }

    /**
     *  丑数
     * @param index
     * @return
     */
    public int getUglyNumberI(int index) {
        if (index <= 0) {
            return 0;
        }
        int num = 0;
        int uglyFound = 0;
        while (uglyFound < index) {
            num++;
            if (isUgly(num)) {
                uglyFound++;
            }
        }
        return num;
    }
    private boolean isUgly(int num) {
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        return num == 1;
    }

    public int getUglyNumberII(int index) {
        if (index <= 0) {
            return 0;
        }
        int[] uglyNumbers = new int[index];
        uglyNumbers[0] = 1;
        int nextUglyIndex = 1;
        int multiply2 = 0;
        int multiply3 = 0;
        int multiply5 = 0;
        while (nextUglyIndex < index) {
            int min = Math.min(Math.min(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3),uglyNumbers[multiply5] * 5);
            uglyNumbers[nextUglyIndex] = min;
            while (uglyNumbers[multiply2] * 2 <= uglyNumbers[nextUglyIndex]) {
                multiply2++;
            }
            while (uglyNumbers[multiply3] * 3 <= uglyNumbers[nextUglyIndex]) {
                multiply3++;
            }
            while (uglyNumbers[multiply5] * 5 <= uglyNumbers[nextUglyIndex]) {
                multiply5++;
            }
            nextUglyIndex++;
        }
        return uglyNumbers[index - 1];
    }


    /**
     * 二叉搜索树与双向链表
     */
    private TreeNode pre = null;
    public TreeNode Convert(TreeNode root) {
        if (root == null) {
            return null;
        }
        inOrder(root);
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }
    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        node.left = pre;
        if (pre != null) {
            pre.right = node;
        }
        pre = node;
        inOrder(node.right);
    }

    /**
     * 序列化/反序列化二叉树,
     * @param root
     * @return
     */
    String serializeStr = "";
    public String Serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
    }
    public TreeNode descrialize(String s) {
        serializeStr = s;
        return descrialize();
    }
    public TreeNode descrialize() {
        if (serializeStr.length() == 0) {
            return null;
        }
        int index = serializeStr.indexOf(',');
        if (index == -1) {
            return null;
        }
        String sub = serializeStr.substring(0, index);
        serializeStr = serializeStr.substring(index + 1);
        if ("#".equals(sub)) {
            return null;
        }
        int val = Integer.valueOf(sub);
        TreeNode t = new TreeNode(val);
        t.left = descrialize();
        t.right = descrialize();
        return t;
    }


    /**
     * 不用加减乘除做加法
     * @param a
     * @param b
     * @return
     */
    public int addUseBit(int a, int b) {
        if (b == 0) {
            return a;
        }
        return addUseBit(a ^ b, (a & b) << 1);
    }

    public int sum1ToN(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sum1ToN(n - 1);
    }

    public int MaxProfit(int[] numbers) {
        if (numbers == null || numbers.length < 2) {
            return 0;
        }
        int min = numbers[0];
        int maxDiff = numbers[1] - min;
        for (int i = 2; i < numbers.length; i++) {
            if (numbers[i - 1] < min) {
                min = numbers[i - 1];
            }

            int curDiff = numbers[i] - min;
            if (curDiff > maxDiff) {
                maxDiff = curDiff;
            }
        }
        return maxDiff;
    }

    /**
     * 约瑟夫环
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        int[] array = new int[n];
        int i = -1;
        int step = 0;
        int cnt = n;
        while (cnt > 0) {
            i++;
            if (i >= n) {
                i = 0;
            }
            if (array[i] == -1) {
                continue;
            }
            step++;
            if (step == m) {
                array[i] = -1;
                step = 0;
                cnt--;
            }

        }
        return i;
    }

    /**
     * 判断是否是顺子
     * @param numbers
     * @return
     */
    public boolean isContinuous(int[] numbers) {
        if (numbers == null || numbers.length < 5) {
            return false;
        }
        Arrays.sort(numbers);
        int zeroCnt = 0;
        int gapCnt = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                zeroCnt++;
            } else {
                break;
            }
        }

        int small = zeroCnt;
        int big = small + 1;
        while (big < numbers.length) {
            if (numbers[small] == numbers[big]) {
                return false;
            }

            gapCnt += numbers[big] - numbers[small] - 1;
            small = big;
            big++;
        }
        return zeroCnt > gapCnt;
    }




    @Test
    public void test() {
        // char[][] m = {{'a','b','c'},{'d','e','f'}};
         // System.out.println(hasPath(m, m.length,m[0].length,"ab".toCharArray()));
        int[] a = {0,1,3,4};
        System.out.println(getMissingNumII(a));
        System.out.println(getMissingNumI(a));
       // System.out.println(addUseBit(1,2));
       // System.out.println(sum1ToN(100));
        /*int[] a = {1,-1};
        System.out.println(findGreatestSumOfSubArrayI(a));
        System.out.println(findGreatestSumOfSubArrayII(a));
        System.out.println(findGreatestSumOfSubArrayIII(a));

        System.out.println(numberOf1AppearTimes(10));*/
        /*Integer[] a = {3,32,0};
        arrangeMinArray(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
*/
        // System.out.println(getUglyNumberI(10));
        // System.out.println(getUglyNumberII(10));
        // System.out.println(GetTranslationCount(12258));
        // System.out.println(longestSubstringWithoutDup("arabcacfr"));
        /*
        ArrayList<Integer> res = minKII(a, 3);
         for (Integer s: res
              ) {
             System.out.println(s);
         }*/
        //printStrPermutation("abc");
        // printToMaxOfNDigitsI(3);
       // printToMaxOfNDigitsII(3);
        // System.out.println(match("abc", "a.c"));
        // System.out.println(match("abc", "a c"));
        // System.out.println(match("abc", "a*"));

        /*int[] res = findNumsAppearOnce(a);
        System.out.println(res[0]);
        System.out.println(res[1]);*/
    }
}
